//Given a string s which represents an expression, evaluate this expression and 
//return its value. 
//
// The integer division should truncate toward zero. 
//
// 
// Example 1: 
// Input: s = "3+2*2"
//Output: 7
// Example 2: 
// Input: s = " 3/2 "
//Output: 1
// Example 3: 
// Input: s = " 3+5 / 2 "
//Output: 5
// 
// 
// Constraints: 
//
// 
// 1 <= s.length <= 3 * 105 
// s consists of integers and operators ('+', '-', '*', '/') separated by some n
//umber of spaces. 
// s represents a valid expression. 
// All the integers in the expression are non-negative integers in the range [0,
// 231 - 1]. 
// The answer is guaranteed to fit in a 32-bit integer. 
// 
// Related Topics 栈 字符串 
// 👍 388 👎 0


package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

//Java：Basic Calculator II
class P227BasicCalculatorIi {
    public static void main(String[] args) {
        Solution solution = new P227BasicCalculatorIi().new Solution();
        // TO TEST
        System.out.println(solution.calculate("1*2-3/4+5*6-7*8+9/10"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        String min = "+-";
        String max = "*/";
        String op = "+-*/()";

        public int calculate(String s) {
            if (s == null || s.equals("")) {
                return 0;
            }
            if (s.startsWith("+") || s.startsWith("-")) {
                s = "0" + s;
            }
            char[] chars = s.toCharArray();
            Stack<String> stackOp = new Stack<>();
            Deque<String> stackNum = new ArrayDeque<>();

            //3*(2-1)-3*2
            //3 2 1 * - 3 2 * -

            StringBuilder num = new StringBuilder();
            for (int i = 0; i < chars.length; i++) {
                char ch = chars[i];
                String str = String.valueOf(ch).trim();
                if (str.length() == 0) {
                    continue;
                }
                if (op.contains(str)) {
                    //数字结束
                    if (min.contains(str) && (i == 0 || !stackOp.isEmpty() && stackOp.peek().equals("(") &&
                            (stackNum.isEmpty() || (!stackNum.isEmpty() && !op.contains(stackNum.peek()))) &&
                            !op.contains(String.valueOf(chars[i + 1])) && num.length() == 0)) {

                        num.append(ch);
                        continue;
                    }
                    if (num.length() != 0) {
                        stackNum.push(num.toString());
                    }
                    if (str.equals("(") || stackOp.isEmpty()) {
                        stackOp.push(str);
                    } else if (str.equals(")")) {
                        while (!stackOp.peek().equals("(")) {
                            stackNum.push(stackOp.pop());
                        }
                        stackOp.pop();
                    } else if (stackOp.peek().equals("(")) {
                        stackOp.push(str);
                    } else {
                        while (!stackOp.isEmpty() && opCompare(stackOp.peek(), str)) {
                            stackNum.push(stackOp.pop());
                        }
                        stackOp.push(str);

                    }
                    num = new StringBuilder();
                } else {
                    num.append(str);
                }
            }
            if (num.length() != 0) {
                stackNum.push(num.toString());
            }
            while (!stackOp.isEmpty()) {
                stackNum.push(stackOp.pop());
            }
            return evalRPN(stackNum);
        }

        public boolean opCompare(String a1, String a2) {
            if (max.contains(a2) && min.contains(a1)) {
                return false;
            }
            return true;
        }

        public int evalRPN(Deque<String> tokens) {
            Stack<String> stack = new Stack<>();
            if (tokens == null || tokens.isEmpty()) {
                return 0;
            }
            while (!tokens.isEmpty()) {
                String token = tokens.pollLast();
                if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                    if (!stack.isEmpty()) {
                        int back = Integer.parseInt(stack.pop());
                        int front = Integer.parseInt(stack.pop());
                        int val = 0;
                        switch (token) {
                            case "+":
                                val = front + back;
                                break;
                            case "-":
                                val = front - back;
                                break;
                            case "*":
                                val = front * back;
                                break;
                            case "/":
                                val = front / back;
                                break;
                        }
                        stack.push(String.valueOf(val));
                    } else {
                        stack.push(token);
                    }
                } else {
                    stack.push(token);
                }
            }
            return Integer.parseInt(stack.pop());
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}